class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
class Solution {
    //再类内定义成员变量：后序遍历结果数组下标。这样的话递归程序内后序遍历数组下标才能正确移动
    int postIndex=0;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        //后序遍历结果数组下标从数组末尾开始
        postIndex=postorder.length-1;
        //调用通过中后序遍历结果构建二叉树的方法
        return buildTreeChild(inorder,postorder,0,inorder.length-1);
    }

    //通过前中序遍历结果构建二叉树的底层方法
    //参数分别为：前序遍历结果数组引用，中序遍历结果数组引用，中序遍历结果数组开始下标以及结束下标
    private TreeNode buildTreeChild(int[] inorder,int[] postorder,int inIndexBegin,int inIndexEnd){
        if(inIndexBegin>inIndexEnd){
            //中序遍历结果中不存在根节点，直接返回
            return null;
        }
        //根据后序遍历结果数组的倒序，依次创建根节点、右子树、左子树
        //先创建根节点
        TreeNode root=new TreeNode(postorder[postIndex]);
        //调用在中序遍历结果数组中寻找对应后序序遍历结果数组中出现的根节点的下标的方法
        int rootIndex=findRootIndex(postorder[postIndex],inorder, inIndexBegin,inIndexEnd);
        postIndex--;
        //通过根节点左侧遍历结果递归创建左子树
        root.left=buildTreeChild(inorder,postorder,inIndexBegin,rootIndex-1);
        //通过根节点右侧遍历结果递归创建右子树
        root.right=buildTreeChild(inorder,postorder,rootIndex+1,inIndexEnd);
        return root;
    }
    //在中序遍历结果数组中寻找对应前序遍历结果数组中出现的根节点的下标的底层方法
    private int findRootIndex(int key,int[]inorder,int inIndexBegin,int inIndexEnd){
        for(int i=inIndexBegin;i<=inIndexEnd;i++){
            if(inorder[i]==key){
                return i;
            }
        }
        return -1;
    }
}